package Ep07_BackTrack.Back20_0051;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/7/5 20:10
 * 说明：n皇后问题
 */

public class Mine {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for(char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(n, 0, chessboard);
        return res;
    }

    public void backTrack(int n, int row, char[][] chessboard){
        if(row == n) {
            res.add(Array2List(chessboard));
            return;
        }

        for(int col = 0; col < n; ++col) { // 这里i++和++i都是等代码执行后才执行的，但是++i性能更好
            if(isValid(row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                backTrack(n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }

    // 结果是一个List，因此用for循环把chessboard的每一行（一维数组）都String.copyValueOf()加紧list中
    private List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();
        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    private boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列（列不动，遍历行）
        for(int i = 0; i < row; ++i) {
            if(chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 行不用检查，因为递归中的for循环是按照列来loop的，在一个for循环中一次只赋一个位置的值，回溯时删除，因此不存在行间重复的情况

        // 检查45°对角（行列同时减，行列更大的区域还没递归或for到因此只需要往[0][0]靠近去判断即可）
        for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if(chessboard[i][j] == 'Q'){
                return false;
            }
        }

        // 检查135°角
        for(int i=row-1, j=col+1; i>=0 && j<n; i--, j++) {
            if(chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}
